﻿/*
题目: 重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

https://leetcode.cn/problems/repeated-dna-sequences/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
#define P 31

    using ULL = unsigned long long;
    vector<string> findRepeatedDnaSequences(string s) {
        unordered_set<ULL> vis;
        int n = s.size();

        ULL hash = 0;
        ULL base = 1;

        for (int i = 0; i < 10; i++) {
            hash = hash * P + s[i];
            base *= P;
        }
        vis.insert(hash);

        unordered_set<string> res;
        for (int i = 10; i < s.size(); i++) {
            hash = (hash * P + s[i]) - base * s[i - 10];

            if (vis.count(hash)) {
                res.emplace(s.substr(i - 9, 10));
            }
            vis.insert(hash);
        }

        return vector<string>(res.begin(), res.end());
    }
};
